Konečný automat

Konečný automat (KA, též FSM z anglického finite state machine, či DFA z anglického deterministic finite automaton) je teoretický výpočetní model používaný v informatice pro studium formálních jazyků. Popisuje velice jednoduchý počítač, který může být v jednom z několika stavů, mezi kterými přechází na základě symbolů, které čte ze vstupu. Množina stavů je konečná (odtud název), konečný automat nemá žádnou další paměť, kromě informace o aktuálním stavu. Konečný automat je velice jednoduchý výpočetní model, dokáže rozpoznávat pouze regulární jazyky. Konečné automaty se používají při vyhodnocování regulárních výrazů, např. jako součást lexikálního analyzátoru v překladačích. V informatice se rozlišuje kromě základního deterministického či nedeterministického automatu také automat Mealyho a Mooreův.

Formální definice

Formálně je konečný automat definován jako uspořádaná pětice $\left(S,\Sigma ,\sigma ,s,F\right)$ , kde:

S je konečná neprázdná množina stavů.
Σ je konečná neprázdná množina vstupních symbolů, nazývaná abeceda.
σ je tzv. přechodová funkce (též přechodová tabulka), popisující pravidla přechodů mezi stavy. Může mít buď podobu S × Σ → S (deterministický automat), nebo S × {Σ ∪ ε} → P(S) (nedeterministický automat), viz níže.
s je počáteční stav, s ∈ S.
F je množina finálních (akceptujících) stavů, F ⊆ S.

Popis činnosti automatu

Na počátku se automat nachází v definovaném počátečním stavu. Dále v každém kroku přečte jeden symbol ze vstupu a přejde do stavu, který je dán hodnotou, která v přechodové tabulce odpovídá aktuálnímu stavu a přečtenému symbolu. Poté pokračuje čtením dalšího symbolu ze vstupu, dalším přechodem podle přechodové tabulky atd.

Podle toho, zda automat skončí po přečtení vstupu ve stavu, který patří do množiny přijímajících stavů, platí, že automat buď daný vstup přijal, nebo nepřijal. Množina všech řetězců, které daný automat přijme, tvoří regulární jazyk.

Deterministické versus nedeterministické automaty

Přechodovou funkci lze definovat také tak, že v každém bodě tabulky není jeden cílový stav, ale celá množina stavů. Takový automat se nazývá nedeterministický konečný automat (oproti deterministickému konečnému automatu, který v každém místě tabulky obsahuje právě jeden cílový stav). Takový hypotetický automat pak při přečtení jednoho symbolu ze vstupu přejde jakoby současně do všech stavů této množiny a ze všech těchto stavů pokračuje čtením dalšího vstupu. Vstup pak nedeterministický automat přijme tehdy, je-li alespoň jeden stav z těch, ve kterých automat nakonec zůstane, prvkem množiny přijímajících stavů.

V přechodové tabulce nedeterministického automatu je také navíc sloupeček pro prázdný vstup, označovaný ε (ε obecně v celé teorii formálních jazyků označuje prázdné slovo; musí platit, že ε ∉ Σ, protože by potom v definici - především přechodové funkce - nebylo jasné, zda "ε" značí symbol z Σ, nebo prázdné slovo). Tyto tzv. epsilon-přechody automat provádí neustále, bez čtení symbolu ze vstupu. Je zřejmé, že teoreticky jich musí proběhnout nekonečné množství, ale prakticky to znamená, že automat přejde do takové množiny stavů, která odpovídá tranzitivnímu uzávěru přes tyto přechody.

Jakkoli se možnost současně provádět více větví výpočtu může zdát užitečná, ve skutečnosti je výpočetní model nedeterministického automatu úplně stejně mocný jako model deterministického automatu, také přijímá pouze regulární jazyk. Ve skutečnosti je relativně triviální převést libovolný nedeterministický automat na deterministický. K tomu stačí „pouze“ původní množinu stavů nahradit její potenční množinou (ovšem tím vzroste počet stavů exponenciálně, na 2ⁿ). Každý stav takto vytvořeného automatu pak odpovídá nějaké množině stavů původního nedeterministického automatu a jsou mezi nimi jednoznačné přechody.

Ukázka činnosti

Jako příklad je možné ukázat následující deterministický konečný automat:

S = (S₀, S₁, S₂)

Σ = (0, 1)

σ viz tabulka:

stav	0	1
S₀	S₀	S₁
S₁	S₂	S₀
S₂	S₁	S₂

s = S₀

A = {S₀}

Pokud má daný automat zpracovat vstup 1011, bude to probíhat takto: Na počátku je automat ve stavu S₀. Na vstup přijde první symbol, jednička. Z tabulky vyplývá, že na příchod jedničky ve stavu S₀ automat reaguje přechodem do stavu S₁. Dále přichází nula, ze stavu S₁ se příchodem nuly přechází do stavu S₂. Poté přichází jednička, ze stavu S₂ se příchodem jedničky přechází do stavu S₂ (tzn. zůstává se ve stejném stavu). Nakonec přichází další jednička, takže automat opět zůstává ve stavu S₂. Stav S₂ nepatří do množiny A, tudíž tento automat vstup 1011 nepřijal, řetězec 1011 nepatří do jazyka přijímaného tímto automatem.

Pro úplnost: tento konečný automat přijímá regulární jazyk řetězců, které vyjadřují binární číslo dělitelné beze zbytku třemi. Číslo 1011₂ = 11₁₀, číslo, které není dělitelné třemi (má zbytek 2, odpovídající výslednému stavu S₂).

Znázornění konečného automatu

Místo relativně nepřehledného (zvláště pro větší automaty) popisu konečného automatu přímo tabulkou se obvykle používá grafické znázornění, na kterém kolečka znázorňují jednotlivé stavy a šipky (s přidruženým vstupním symbolem) mezi těmito kolečky popisují jednotlivé přechody. Příklad takového znázornění pro předchozí ukázkový automat je na obrázku:

Dvojité kolečko označuje přijímající stavy (v našem případě pouze jeden, S₀), počáteční stav je označen šipkou směřující z volného prostoru k počátečnímu stavu (v našem případě je jím tedy S₀), někdy s připsaným textem, např. START. (Tato notace není jediná, jindy se např. koncové stavy označují tlustším orámováním a dvojité kolečko označuje počáteční stav apod.)

Zadání konečného automatu

Automat se zadává také pomocí regulárního výrazu, jejichž formalizmus má stejnou vyjadřovací sílu. Regulární výrazy (s rozšířeními) se používají v praxi pro zadávání automatů počítačům. (Častěji než tabulka nebo obrázek.)

Související články

Externí odkazy

Obrázky, zvuky či videa k tématu konečný automat na Wikimedia Commons